<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>C++ Tutorial: Standard Template Library I</title>
  <meta
 content="C++ Tutorial: Standard Template Library II - Maps"
 name="description" />
  <meta
 content="C++ Tutorial, Standard Template Library, STL, Maps"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right">
<a href="../gif.html">Gif</a> 
|<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../Algorithms/algorithms.html">Algorithms</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
| <a href="../python/pytut.html">Python</a> 
| <a href="../CSharp/.netframework.html">C#</a>
| <a href="../forums.html">Forums</a> 
| <a href="../VisualBasicSQL/introduction.html">Visual Basic</a>
</div>
</div>

<div id="contenttext">

<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>

<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>
<br />
<br />
<br />
<br />
<div style="padding: 10px;"><span class="titletext">C++ Tutorial - Standard Template Library II - Maps</span></div>
<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>   
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL) I</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="stl4_algorithms.html">Standard Template Library (STL) IV - Algorithms</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>
</ul>
</div>
<br />
<br />
<img src="images/stl2/Sorak.png" alt="Sorak"/>
<br />
<br />



<div class="bodytext" style="padding: 12px;" align="justify">
<div class="subtitle" id="stl">Standard Template Library (STL) II - Associative Containers</div>
<p>A <strong>map</strong> is an ordered sequence of pairs (key, value) in which we can look up a value based on a key. Data structures similar to <strong>map</strong> are <strong>associative arrays</strong>, <strong>hash tables</strong>, and <strong>red-black trees</strong>.</p>
<br />
<div class="subtitle_2nd" id="associativecontainers">Associative Containers</div>
<ul>
	<li>
	<strong>map</strong>	an ordered container of (key,value) pairs 
	</li>
	<li>
	<strong>set</strong>	an ordered container of keys
	</li>
	<li>
	<strong>unordered_map </strong>	an unordered container of (key,value) pairs 
	</li>
	<li>
	<strong>unordered_set</strong>	an unordered container of keys
	</li>
	<li>
	<strong>multimap</strong>	a <strong>map</strong> where a key can occur multiple times
	</li>
	<li>
	<strong>multiset</strong>	a <strong>set</strong> where a key can occur multiple times
	</li>
	<li>
	<strong>unordered_multimap</strong>	a <strong>unordered_map</strong> where a key can occur multiple times
	</li>
	<li>
	<strong>unordered_multiset</strong>	a <strong>unordered_set</strong> where a key can occur multiple times
	</li>
</ul>
<br />
<br />
<div class="subtitle" id="stl">Maps</div>
<p>What is a map?<br />
The map class template looks like this:</p>
<pre>
std::map&lt;Key, Data, Compare, Alloc&gt;
</pre>
<p>
STP map implementations are more like a balanced binary search trees (BST). To be more specific, they are <strong>red-black trees</strong>. </p>
<img src="../images/cplusplus/Red-black.png" alt="red-black"/>
<p>Picture source: <a href="http://en.wikipedia.org/wiki/Red-black_tree" target="_blank">http://en.wikipedia.org/wiki/Red-black_tree</a></p>
<p>A tree is built up from <strong>nodes</strong>. A <strong>node</strong> holds a key, its corresponding value, and pointers to two descendants' <strong>node</strong>s. We won't go into details, but one thing we should remember is that the red-black tree has guaranteed log(n) height tree. </p>
<p>Let's look at the simple code which shows how to use maps.</p>
<pre>
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;string&gt;
#include &lt;utility&gt; 
using namespace std;
 
int main()
{
	typedef map&lt;string, int&gt; mapType;
	mapType populationMap;
 
	populationMap.insert(pair&lt;string, int&gt;("China", 1339));
	populationMap.insert(pair&lt;string, int&gt;("India", 1187));
	populationMap.insert(mapType::value_type("US", 310)); 
	populationMap.insert(mapType::value_type("Indonesia", 234)); 
	populationMap.insert(make_pair("Brasil", 193)); 
	populationMap.insert(make_pair("Pakistan", 170)); 

	// Erase the end element using the erase function
	// Because it's ordered map (by key), 
	// map elements are not in the order of the entry 
	// In this map it's US since it's ordered alphabetically.
	mapType::iterator iter = --populationMap.end();
	populationMap.erase(iter);
 
	// output the size of the map
	cout << "Size of populationMap: " << populationMap.size() << '\n';
 
	for (iter = populationMap.begin(); iter != populationMap.end(); ++iter) {
		cout << iter->first <<": " 
			<< iter->second << " million\n";
	}

	// find will return an iterator to the matching element if it is found
	// or to the end of the map if the key is not found
	string country("Indonesia");
	iter = populationMap.find(country);
	if( iter != populationMap.end() ) 
		cout << country <<"'s populations is "
			<< iter->second << " million\n";
	else
		cout << "Key is not in populationMap" << '\n';
 
	// clear the entries in the map
	populationMap.clear();
}
</pre>
<p>Output from the run is:</p>
<pre>
Size of populationMap: 5
Brasil: 193 million
China: 1339 million
India: 1187 million
Indonesia: 234 million
Pakistan: 170 million
Indonesia's populations is 234 million
</pre>
<p>To use a map, we must include the header file &lt;map&gt;</p>
<pre>
#include &lt;map&gt;
</pre>
<p>Let's look at the sample program counting the number of words in the input file.</p>
<p>When we define: </p>
<pre>
map&lt;string, int&gt; 
</pre>
<p>the first template argument is the type of the element's <strong>key</strong>, and the second template argument is the type of the element's <strong>value</strong>.</p>
<p>The template for the map defined inside namespace std is:</p>
<pre>
namespace std {
	template &lt;class Key, class T,
			class Compare = less&lt;Key&gt;,
			class Allocator = allocator&lt;pair&lt;const Key, T&gt; &gt; &gt;
	class map;
</pre>
<p>The elements of a map may have any types of <strong>key</strong> and <strong>value</strong> that meet the following two requirements:</p>
<ol>
	<li>The key/value pair must be assignable and copyable.</li>
	<li>The key must be comparable with the sorting criterion.</li>
</ol>
<p>In the code: </p>
<pre>
	populationMap.insert(pair&lt;string, int&gt;("China", 1339));
	populationMap.insert(pair&lt;string, int&gt;("India", 1187));
	populationMap.insert(mapType::value_type("US", 310)); 
	populationMap.insert(mapType::value_type("Indonesia", 234)); 
	populationMap.insert(make_pair("Brasil", 193)); 
	populationMap.insert(make_pair("Pakistan", 170)); 
</pre>
<p>we are inserting a key/value pair in three different ways:</p>
<ol>
	<li><strong>Use pair&lt;&gt;</strong> <br />
	Use pair&lt;&gt; directly. <br />
<pre>
pair&lt;string, int&gt;("India", 1187));
</pre>
	</li>
	<br />
	<li><strong>Use value_type</strong> <br />
	To avoid implicit type conversion, we pass the correct type explicitly by using <strong>value_type</strong>, which is provided as a type definition by the container type. <br />
<pre>
populationMap.insert(mapType::value_type("US", 310));
</pre>
	<br />
	<li><strong>Use make_pair</strong> <br />
	The most convenient way is to use <strong>make_pair</strong> function. This function produces a pair object that contains the two values passed as arguments:
<pre>
populationMap.insert(make_pair("Brasil", 193));
</pre>
	</li>
</ol>
<p>Then when we tried to erase the element at the end, we used '--' operator on the iterator <strong>end()</strong> because it is pointing to the one passed the end element.</p>
<pre>
	mapType::iterator iter = --populationMap.end();
</pre>
<br />
<br />


<div class="subtitle_2nd" id="wordcount">Maps for Word Count</div>
<p>Following code counts the word using maps.<br />
It first reads in the Stairway To Heaven Lyrics (Led Zeppelin), then put it into a map&lt;string,int&gt;. The first string argument is the word and the second argument is the counter which shows how many times the key appeared in the lyric. </p>
<pre>
#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;map&gt;
#include &lt;algorithm&gt;
#include &lt;string&gt;
#include &lt;iterator&gt;
using namespace std;
int main()
{
	const string delims(" \t,.;");
	map&lt;string,int&gt; words;
	string line, str;
	ifstream myFile("stairwaytoheaven.txt", ios_base::in);
	while (getline(myFile,line)) {
		string::size_type beg, end;
		beg = line.find_first_not_of(delims);
		while (beg != string::npos) {
			end = line.find_first_of(delims,beg);
			if(end == string::npos) {
				end = line.length();
			}
			str.assign(line,beg,end-beg+1);
			++words[str];
			beg = line.find_first_not_of(delims,end);
		}
	}
	typedef map&lt;string,int&gt;::const_iterator iter;
	for(iter p = words.begin(); p != words.end(); ++p)
		cout << p->first << ":" << p->second << endl;

	myFile.close();
	return 0;
}
</pre>
<p>Output should look like this:</p>
<pre>
'Cause :1
All :1
And :12
Aw,:1
But :2
Dear :1
Don't :1
Echo :1
For :3
How :1
I :3
If :3
In :3
It's :1
May :1
Misgiven :1
Oh,:1
Ooh,:5
Our :1
Rings :1
Sometimes :1
.......
whispering :1
white :1
who :2
who's :1
whoa,:5
will :4
wind :2
wind? :1
with :1
won't :1
wonder :5
word :1
words :1
you :8
you're :1
your :1
</pre>
<p>To extract a word from a string, we use several separators (delimiters) as in the line:</p>
<pre>
const string delims(" \t,.;");
</pre>
<p>It include space, tab, '.', and ';'.</p>
<p>Then we find the beginning and end of the word in between the delimiters:</p>
<pre>
beg = line.find_first_not_of(delims);
		while (beg != string::npos) {
			end = line.find_first_of(delims,beg);
</pre>
<p>Then we assign the word extracted to a string "str" while incrementing the count:</p>
<pre>
			str.assign(line,beg,end-beg+1);
			++words[str];
</pre>
<br />
<br />


<div class="subtitle_2nd" id="hashtablevsmap">Hash Table vs. STL map</div>
<p>Compare a <strong>hash table</strong> vs. an <strong>STL map</strong><br />
How we implement hash table? <br />
Instead of hash table, what data structure options can be used for the case when the number of input is small?</p>
<ul>
	<li><strong>Hash Table </strong> <br />
	<ul>
		<li>A value is stored by applying hash function on a key. So, values are not stored in sorted order.</li>
		<li>Because hash table uses the key to find the index that will store the value, an insert/loopkup can be done in O(1) time if we can assume there are only a few collisions in the hash table.</li>
		<li>Potential collisions should be handled properly.</li>
	</ul>
	</li>
	<li><strong>STL map</strong> <br />
	<ul>
		<li>Insertion of key/value is in sorted order of key.</li>
		<li>It uses a tree to store values - O(logN) insert/lookup.</li>
		<li>No need to handle collisions.</li>
		<li>An STL map works well to:</li>
		<ul>
			<li>find min/max element</li>
			<li>print elements in sorted order</li>
			<li>find the exact element or if the element is not found, find the next smallest number.</li>
		</ul>
		</li>
	</ul>
	</li>
</ul>
<p>So, how a hash table implemented? </p>
<ul>
	<li>A good hash function is needed to ensure that the hash values are uniformly distributed.</li>
	<li>A collision protection method is required: 
		<ul>
			<li>chaining - for dense table entries.</li>
			<li>probing - sparse table entries. </li>
		</ul>
	</li>
	<li>Implement methods to dynamically increase or decrease the hash table size on a given criterion.</li>
</ul>
<p>When the number of inputs is small, we can use STL map as an option for data structure. Since n is small, O(logN) is negligible.</p>
<br />
<br />
<br />
<br />
<img src="images/stl2/GokSung.jpg" alt="GokSung"/>
<br />
<br />


<p>In the following Chapters, we'll look at <strong>iterators</strong>, and <strong>algorithms</strong> in detail.</p>
<br />
<br />
<div id="rightpanel">
<div align="center">
</div></div>

<br /><br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL) I</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="stl4_algorithms.html">Standard Template Library (STL) IV - Algorithms</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>
</ul>
<br /><br />


<br />


<br />
<br />
<br />


</div>
</div>
<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2011 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a>
</div>
</div>
</div>
</body>
</html>
